集训 DS 题记录

2023 年 7 月。老师是 jt。讲的题有很多好技巧。其实没有讲新的数据结构，不会的还是不会 QAQ。

Ice-cream Tycoon

SGU 311/ Gym101365 F

增加 n 个价格为 c 的物品，但是最终可能同时存在至多 $10^{12}$ 个数，显然平衡树存不下。

但是这些数值域很小，$c\leq10^6$，类似雨天的尾巴，我们考虑开桶来维护（权值线段树嘛）。

通过线段树上二分可以找到前 n 小的数。这是一个前缀清空。注意最后一个桶不一定被清空，这里单点修改即可。然后这些数的和也可以通过线段树简单维护。

New Year Tree

CF 620 E

回来吧我的 lg RMJ，我最骄傲的信仰

在写完这篇文章之前，RMJ 堂堂复活！

简单题。首先经典套路把子树问题转化成区间问题（dfs 序）。现在就变成区间上色（区间赋值）和查询区间内颜色个数了。注意到颜色数量 c<61，那么我们直接用线段树暴力维护区间内的颜色集合。

也就是，线段树的每个节点维护对应区间有哪些颜色，用一个 long long 存，如果有颜色 i 那么第 i 位就是 1，否则就是 0。那么区间的信息并就是或运算：t[p]=t[lson]|t[rson]。显然 $\{\mathbb{N},|\}$ 是一个幺半群。最后查询颜色个数，就是先查询区间的颜色集合，再 popcount 一下就好了。

Ping-Pong

CF 319 E

10 min 速切了。但是好像有些结论切的时候没细想，虽然是对的，但是是猜的 QAQ。

这道题的线段树用得很神奇。

首先这是一个特殊的有向区间图。两个区间只有三种关系，包含，相交（但不包含），相离。若两个区间包含，则是小区间向大区间连边；若两个区间相交，则是双向边；否则，没有边。

以下记 $A\to B$ 是 A 可达 B，$A\not\to B$ 是 A 不可达 B。

显然若区间 A 交 B，B 交 C，A 交 D... 那么它们构成一个强连通分量。我们直接把它们用一个大区间来表示（但不是替换）：$S=[\min\{A_l,B_l,C_l,D_l,\dots\},\max\{A_r,B_r,C_r,D_r,\dots\}]$。记 A,B,C,D... 为 S 的子区间。这些大区间有一些性质。

1. S 两两之间只有包含和相离两种关系；
2. 对于任意一个 S，S 的子区间间相互可达；
3. S 的子区间把 S 完全覆盖；
4. 若 $A\subseteq S_A,B\subseteq S_B$，那么，若 $S_A\subsetneqq S_B$ 则 $A\to B$ 且 $B\not\to A$。
5. 不存在 $A\subseteq S_A,B\subseteq S_B$， $S_A$ 和 $S_B$ 有交（但不包含）。

前三个性质很简单，关键是第四个。首先，对于每个 A 的子区间，都不存在 B 的子区间跟它有交，反之亦然，否则 A 和 B 应当合成一个大区间。其次，A 的每个区间不可能跟 B 的所有区间相离，根据性质 3 容易得到。接着考虑反证。若 $A\not\to B$，则 A 的每个子区间都包含 B 的某个子区间，但是 B 的最左边区间或最右边区间一定不完全被包含，矛盾。那么 A 的每个子区间都被 B 的每个子区间包含，那么 $B\not\to A$。

第五个性质可以类似第四个性质证明。

那么对于每个区间，用并查集维护它对应的大区间。若询问 $A\to B$ 正确性，只需查询 A 和 B 是否在一个大区间中，或者 A 的大区间被 B 包含，或者 A=B。

题目中有一个性质：新加入的区间一定是最长的。这个性质有什么用呢？保证每个区间跟它只有交，没有别的区间在加入时包含它。因此我们只需要把它跟包含它左端点的合并，跟包含它右端点的合并即可。

具体怎么合并呢？这是最难的问题。现在来到了线段树的奇妙用法。我们知道线段树把任一个区间分成 $O(\log n)$ 段。对于每一段，我们都在对应节点上存储覆盖它的区间编号。那么，对于左端点/右端点查询被包含，只需找从叶子结点到根节点的那条链上记着的区间标号，并把那些区间删除，然后用这个区间替换。每个区间只会被加一次，然后删除 log n 次（log n 段都被删了）。那么复杂度是 log n 的，加上并查集总复杂度应该是 $O(n\log n\ \alpha (n))$。

这个实现可能略显难，可以结合代码理解（贴在文末）。

Life as a Monster

GYM 100739 E

经典切比雪夫距离转曼哈顿距离题，把每个点 S(x,y) 替换成 D(x+y,x-y)，那么 S 相互之间的切比雪夫距离就是 D 相互之间的曼哈顿距离的二分之一。

强制在线可以用平衡树解决。

Tourists

CF 487 E

现在是，口胡时间。

先建立点双圆方树，至于怎么建，我也不知道，以后就知道了。

那问题就转化成求在圆方树 (u,v) 路径上经过的每个方点连接的所有圆点中的最小权值。然后就树剖一下就好了。

但是问题在于，一个圆点可能连接多个方点，这样修改的复杂度不对。技巧是把圆方树看做有根树，每个方点维护自己的儿子的最小值（与上面的区别就是，方点不维护父亲）。那么这样修改就只与一个方点有关了，答案也不受影响。注意要特判，路径的拐点（LCA)，如果是方点，那么要把它的父亲圆点也算上。

New Year and Conference

CF 1284 D

其实本题 O(n log n) 是 trivial 的。我们把问题改成判断，有两个数轴，上面分别有一些一一对应的区间，问是否存在一些第二个数轴上有交的区间，第一个数轴上对应的区间完全没有。

注意到区间太多了没用，其实只需要判断在第二个数轴上选两个区间就行了。因此 $O(n^2)$ 的做法很显然。然后我们只需要先给第二个数轴按左端点排个序，用一个数据结构（比如 set）维护跟当前区间有交的，在第一个数轴上右端点最小的区间和左端点最大的区间，判断一下是否有交即可。复杂度 O(n log n)，可过此题。

但是我们还有一个除排序核心算法 O(n) 的做法。首先分别给两个数轴的区间排个序。做一个 hash，$H_s=\sum_{\text {区间}\ i,j\ \text {在第}\ s\ \text{个数轴有交}} v_iv_j$，其中 $v_i$ 是对区间 i 随机的赋的一个权值（注意两个数轴对应区间权值应当相同）。然后 O(n) 扫一遍分别求出 $H_1,H_2$。那么，如果 $H_1=H_2$，那说明对于任意两个区间 $i,j$，若在第一个数轴有交 ，则在第二个数轴有交，也就是命题不成立。否则命题成立。

还可以直接使用 xor hash，也就是对每一个区间，它的 hash 值为 $H_{s,i}=\bigoplus_{\text {区间}\ i,j\ \text {在第}\ s\text{个数轴有交}} v_j$，其中 $\oplus$ 表示异或。只需判断对于每一个区间，$H_{1,i}=H_{2,i}$ 即可。这个的正确性我不是很懂，但无论怎样在 CF 上可以过。

其实上面两个 hash 算法整体也可以是 O(n) 的，因为可以用对结构体的基数排序。

Tree Generator™

CF 1149 C

™ 符号可以用微软输入法打出来

现在是，口胡时间。（口胡完了，写的时候发现有点错嘞，已改）

括号序可以反映出什么？可以联想到括号匹配的过程，我们把左括号赋成 1，右括号赋成 -1。那么到达一个节点是，括号序的前缀和就是它的深度。

直径除了搜索解法，还有什么？dp 解法。类似 dp 解法，我们就是要求任选两个点，最大的距离。

树上距离需要 LCA，回忆 LCA 有什么求法？注意到括号序的构造过程是 dfs，那么一定满足 dfs 序的性质：两个点的 LCA 是它们在 dfs 序中，构成的区间内的最早被遍历到的节点。类似的也可以改为构成的区间中深度最小的。

那么就是，依次选取括号序上三个点 u,v,l，且 l 是 u,v 的 LCA。求 $d_u+d_v-2d_l$ 的最大值。又注意到 $d_l$ 是 $[u,v]$ 的最小值，那么直接求 $\max_{u\leq l\leq v}d_u+d_v-2d_l$，而不必满足 lca，也是等价的。

这样我们可以考虑用线段树维护。初始每个叶子结点按括号，值为 1/-1。首先肯定要维护区间 ans 嘛。然后呢，由于 $d$ 是前缀和，所以还要维护区间的 sum，在上传信息时，右边的信息必须要加上左边区间的 sum 是吧。

然后考虑合并的时候怎么做。分类讨论：

1. u,v,l 都在左儿子区间，那么贡献是 $ans_l$；

2. u,v,l 都在右儿子区间，那么贡献是 $ans_r+(sum_l+sum_l-2sum_l)=ans_r$（加上左区间 sum 是因为 d 是前缀和嘛）；

3. u,l 在左区间，v 在右区间，那么贡献是 $\max \{d_u-2d_l\}+(max_r+sum_l)$。也就是我们还要维护区间最大值；

4. u 在左区间，l,v 在右区间，那么贡献是：

最后 ans 就会被更新成上述四个情况贡献的最大值。

根据上文我们还要维护 $\max \{d_u-2d_l\}$ 和 $\max\{d_v-2d_l\}$。也可以分类讨论。两个点都在同一个区间，做法是 trivial 的。这里只讨论分别在两个区间中的情况：

• $\max \{d_u-2d_l\}$：答案是 $max_l-2min_r-2sum_l$。
• $\max\{d_v-2d_l\}$：答案是 $max_r-2min_l+sum_l$。

所以还要维护一个区间最小值。然后这个题就做完了。信息比较复杂，但是具体写起来也不难，注意一下初值就好了。由于只有单点修改，可以考虑 zkw 线段树。（统计的力量！）

Roadside Trees

CF 264 E

不可以口胡，总司令。

这道题的关键点在于刚种下去的树高 $\leq 10$ 并且砍掉的树的次序 $\leq 10$，并且不存在相同高度的树。

所有树每秒长 1 m，那么相对高度不变。假设某棵树种下去时间为 t，那么只要把它的高度设置成 h-t，就不必考虑树长高的影响了。

回忆最长上升子序列是怎么做的：$dp(i)=\max\limits_{1\leq j<i,h_j<h_i} \{dp(j)\}+1$。

但是由于这道题砍的是前十棵树，自然的可以考虑倒着求最长下降子序列（其实没什么区别）：$dp(i)=\max\limits_{i<j\leq n,h_i<h_j} \{dp(j)\}+1$。这样，可以使砍完树发生变化的 dp 值更少。

树高小于等于 10 意味着，这棵树种下去的一刻，比他矮的最多只有 10 颗。那么种树的时候，排除掉比他矮的 10 棵，它的 dp 值就是它的后缀 max 加一。可以开一棵定义域为下标的线段树，维护后缀 dp max，种树的时候暴力删掉那 10 棵树，就能更新出新种的树的 dp 值，然后把删掉的树按照下标插入回来，更新其 dp 值。（不能用树状数组，因为排除比他矮的 10 棵这个过程不是取 max 操作。）

而砍掉的树的次序不超过 10，意味着受影响的 dp 只有这棵树前面的 10 棵树。类似的，我们开一棵定义域为树高的线段树，维护后缀 dp max。砍树的时候暴力删掉前 10 棵树，再按照树高倒序插入回来，更新它的 dp 值。

总复杂度就是 $O(n\log n)$ 的了，并且常数为 10。由于单点操作的原因，可以用 zkw 线段树。

Noble Knight's Path

CF 226 E

最后一道题了，真的。

其实思路很简单这题，就是几个数据结构套一起很阴间。先考虑最简单形式，也就是询问只有从 0 年到现在，树是一条编号递增的链。这个就简单了，用一棵线段树维护点是否被亵渎，然后线段树上二分即可。

那么剩下的也“简单”了，线段树改成可持久化线段树（由于一个城池只会被亵渎一次这样做可行），然后树上问题，上个树剖即可。如果是对整棵树开线段树，那么就是区间上二分；如果对每条链开线段树，就是前后缀上二分。复杂度 $O(n \log^2 n)$。

说的这么简单也只是说的简单而已了。黑题有黑题的原因……这道题我写了将近 7k。

终于写完了 XD。DS 专题剩下的题我直接放弃。

代码

鉴于所有代码加起来，实在太长了。我就只放上文提到要放代码的了。

Ping-Ping

Noble Knight's Path